Fair Path Sampling in One Shot Neural Architecture Search

34 concepts24 papers1 proposal

One-Shot Neural Architecture Search (NAS) drastically reduces the computational cost of finding optimal deep learning models. Instead of training thousands of candidate networks from scratch, one-shot methods train a single, massive weight-sharing supernet that encompasses the entire search space. Every individual architecture (or sub-network) is simply a specific "path" through this supernet.

Once the supernet is trained, we can evaluate any sub-network instantly by freezing the supernet's weights and running validation data through that specific path. However, this approach introduces a fundamental flaw: how do we ensure that the supernet trains all paths equally so that its performance rankings are actually reliable?

The Core Problem: Optimization Bias

When a supernet is trained using a traditional controller (like a Reinforcement Learning agent) or joint gradient-based optimization, the system naturally favors paths that yield quick rewards or low loss early in training.

For example, simple operations like skip connections or smaller sub-networks converge much faster than complex convolutions. As Barry Dong et al. and Yin Zheng et al. observe, these fast-converging operations quickly dominate the shared weights, starving more complex but ultimately superior paths of training updates.

This creates a severe optimization bias (or sampling bias). The supernet becomes an unreliable proxy because a sub-network's performance inside the supernet reflects how fast it converged early on, rather than its true potential when trained independently from scratch.

Standard Training (Biased):
[Iteration 1] -> Chooses Skip Connection (Fast convergence!)
[Iteration 2] -> Chooses Skip Connection (Lower loss, preferred by controller)
[Iteration 3] -> Chooses Skip Connection 
Result: Convolution paths are starved of updates and underperform.

Fair Path Sampling:
[Iteration 1] -> Path A (Conv 3x3) updated
[Iteration 2] -> Path B (Conv 5x5) updated
[Iteration 3] -> Path C (Skip Conn) updated
Result: All operations are optimized equally regardless of early convergence speed.

The Solution: Decoupling and Uniform Sampling

To fix this "rich get richer" dynamic, researchers introduced a deceptively simple idea: completely decouple the supernet weight optimization from the architecture search policy.

In their Single Path One-Shot (SPOS) framework, Xiangyu Zhang et al. proposed training the supernet by uniformly sampling a single random path at each iteration. Because every operation has an equal mathematical probability of being chosen, no single path can monopolize the gradients. This ensures that all operations are optimized equally, providing a balanced baseline for the subsequent search phase. This uniform stochastic path sampling approach has been widely adopted across diverse domains, from federated medical imaging (Holger R Roth et al.) to neural ensemble generation (Yao Shu et al.).

Enforcing Strict Fairness

While uniform random sampling helps over long training horizons, it still introduces stochastic noise—by pure chance, some paths might still be sampled more than others within a given epoch. To eliminate this entirely, Xiangxiang Chu et al. (FairNAS) proposed Strict Fairness.

Instead of independent random choices at each step, they sample paths without replacement within each training step. If a layer has four candidate operations, the training routine forces the supernet to activate and update each of those four operations exactly once before any operation can be sampled again.

As Jixiang Li et al. and Yu Xue et al. demonstrate, this strict step-level fairness ensures that the final performance rankings reflect structural merit rather than training frequency.

To handle irregular search spaces where layers have an unequal number of choices, Xiangxiang Chu et al. introduce a preprocessing step where choices are randomly duplicated to maintain a uniform count across all layers, allowing strict fairness mechanisms to execute seamlessly.

Mitigating Structural and Dimensional Biases

Optimization bias doesn't just happen across discrete operations; it also manifests across structural dimensions like network depth, width, and channel sizes.

Subnet Size and Complexity Bias

Smaller sub-networks inherently require fewer updates to converge. If left unchecked, the search process can prematurely collapse into sub-optimal, low-complexity models. Yifan Jiang et al. address this with fairness-aware channel selection, ensuring all candidate widths receive equal update opportunities. Similarly, when stitching together vision transformers of different scales, Zizheng Pan et al. utilize resource-constrained sampling to select sub-networks uniformly across different computational complexity ranges, preventing the optimization from biasing toward specific model scales.

Sampling Bias vs. Weight Interference

In Once-For-All (OFA) networks, performance disparities were long assumed to be caused by "weight interference" between subnets. However, Jordan Shipard et al. demonstrated that sampling bias is the true culprit. By introducing Random Subnet Sampling (RSS) uniformly across all dimensions (width, depth, kernel size) throughout the entire training process, they showed that treating every potential sub-network size as equally important eliminates the need for complex, multi-stage training schedules.

Subspace Imbalance

When a search space is partitioned, some subspaces may contain vastly more architectures than others, causing the supernet to spend disproportionately more time optimizing larger regions. Youngmin Oh solved this by grouping architectures by their nonlinearity count (the number of ReLU activations) and employing a balanced sampling strategy that selects exactly one subnet from each available subspace per iteration, preventing larger search regions from dominating.

Ordinal vs. Cyclic Weight Sharing

In width or channel search, standard weight sharing is "ordinal"—it always activates the first $k$ channels. This means lower-indexed channels get over-optimized because they are used by every single subnet size. To counter this, Xiu Su et al. proposed a cyclic weight-sharing mechanism that rotates the active indices rather than always starting from zero, ensuring uniform gradient contributions across all available channels.

Ordinal Weight Sharing (Unfair):
Subnet Width 1: [X][ ][ ][ ]
Subnet Width 2: [X][X][ ][ ]
Subnet Width 3: [X][X][X][ ]
-> Channel 0 is updated 3x; Channel 2 is updated 1x.

Cyclic Weight Sharing (Fair):
Subnet Width 1 (Shift 0): [X][ ][ ][ ]
Subnet Width 1 (Shift 1): [ ][X][ ][ ]
Subnet Width 1 (Shift 2): [ ][ ][X][ ]
-> Active indices rotate, balancing the gradient updates across all channels.

Why It Works: The Order-Preserving Property

The ultimate goal of fair path sampling is to preserve the global ranking order of architectures (the "order-preserving" property). We do not need the supernet's validation accuracy to perfectly match standalone accuracy down to the absolute decimal; we just need the relative ranking of architectures to hold true.

If a supernet is trained unfairly, a mediocre architecture that happened to be sampled frequently will outperform a superior architecture that was starved of updates. By ensuring that every connection, operation, and dimension is activated an equal number of times—as emphasized by Zhichao Jiang et al. and Gengwei Zhang et al.—the supernet's internal weights become an accurate, unbiased proxy for standalone performance. This global order-preserving capability provides a reliable foundation that allows subsequent search algorithms (such as evolutionary search or fine-tuning) to confidently select the truly optimal architecture.

Key Foundational Work

Neural Architecture Search on Acoustic Scene Classification (2020) — contributed 2 concept elements to this direction.
One-Shot Neural Architecture Search via Self-Evaluated Template Network (2019) — contributed 2 concept elements to this direction.
Auto-Panoptic: Cooperative Multi-Component Architecture Search for Panoptic Segmentation (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fair_path_sampling_bc2ddb1c,
  title = {fair path sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-path-sampling/rdr_bc2ddb1ce1c24e20a16730a01fb6e13b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_fair_path_sampling_bc2ddb1c_v1,
  title = {fair path sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-path-sampling/rdr_bc2ddb1ce1c24e20a16730a01fb6e13b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake