Do Greedy Architecture Searches Throw Away the Networks That Travel?

Automated architecture search builds neural networks by trying small edits, such as a wider layer, a different kernel, or a dropped connection, and keeping the edits that help. "Help" is almost always measured on validation data drawn from the same place as the training data. In clinical machine learning, that place is usually one or a few hospitals. A model that does well there often fails at a new hospital with different scanners, stains, or patient mix. Clinicians check this through external cohort validation: the design is locked, then tested once on data from an institution that took no part in building it. This note asks whether the step-by-step, keep-what-helps logic of greedy search systematically removes the architectures that would have survived that test. It also asks whether search methods that can accept temporary losses recover those architectures when the reward measures cross-hospital transfer instead of in-hospital fit.

The opportunity is that both fields have identified a failure, and neither has tested whether the two failures are linked. Architecture-search work shows that greedy methods stall on plateaus and discard branches that need a temporary dip before paying off. External-validation work shows that in-hospital metrics reward site-specific shortcuts. If the in-hospital reward surface and the cross-hospital reward surface have different local optima, then switching only the reward or only the search algorithm may each be insufficient. We propose to measure this directly on an exhaustively trained architecture space, using hospital-split histopathology data and keeping the external hospital strictly locked away.

Core Claim

We claim, and will test, two things. First, a reward built only from derivation hospitals predicts external-hospital performance much better than ordinary in-hospital validation accuracy. That reward trains on all but one derivation hospital, scores on the held-out one, and keeps the worst case. Second, this cross-hospital reward surface is more rugged than the in-hospital surface: it has more local optima under single-edit moves, after accounting for seed noise. Consequently, a non-greedy search that optimizes over whole architectures should beat greedy hill-climbing by a larger margin under the cross-hospital reward than under the in-hospital reward. An example of such a search is dynamic-programming decoding over a chain-structured space.

If the second claim fails, meaning greedy search under the cross-hospital reward does as well as global search, the useful contribution reduces to "change the reward." We will report that outcome as such. The two-by-two design below is built to tell these cases apart.

Formally, let $a$ be an architecture and $\mathcal{H}=\{1,2,3\}$ the derivation hospitals. Let $\mathrm{acc}_k(a)$ be the accuracy on hospital $k$ of $a$ trained on $\mathcal{H}\setminus\{k\}$. The search reward is

$$R(a) = \min_{k \in \mathcal{H}} \mathrm{acc}_k(a),$$

which uses no data from the external hospitals. We take the worst case rather than the mean because the external site is unknown, and the method should not reward architectures that transfer well only to an easy neighbour.

Where This Sits Relative to Prior Work

The architecture-search papers motivate the second claim. Simple and efficient architecture search for Convolutional Neural Networks (NASH, greedy hill-climbing with function-preserving network edits) reports plateaus where no single edit helps, so escaping them requires several non-improving steps. Search Tree Pruning for Progressive Neural Architecture Search finds that depth-first progressive search discards children that fail to beat their parent within a short training horizon. Efficient Transfer Learning via Joint Adaptation of Network Architecture and Weight shows that networks with equal source accuracy diverge on a downstream task. All three measure the trap against in-distribution reward. None asks whether the trap changes shape when the reward is transfer to a new site.

Two papers supply our methods. AOWS recasts channel-width choice as a chain-structured Markov random field, a model where each layer's choice is scored alone and jointly with its neighbour, and decodes the best whole configuration with the Viterbi algorithm. On ImageNet it beats greedy AutoSlim, 27.5% versus 28.5% top-1 error. We reuse this decoding with a different objective. Neural Architecture Search in A Proxy Validation Loss Landscape (PVLL-NAS) learns a surrogate network that predicts validation loss from an architecture encoding and navigates it by gradients. We use it as a second non-greedy arm.

SGAS is the strongest argument that greedy is fine. Its sequential edge commitment raises the rank correlation between search and final evaluation to Kendall τ 0.56, against 0.16 for DARTS. However, that correlation is in-distribution, and our first measurement checks whether it holds when the target is an external hospital.

The closest attempts at this intersection each differ on a point that matters. G-NAS searches only a detector's prediction head under a loss that depends on the split between classification and box regression, on driving imagery. Adapting Neural Architectures Between Domains (AdaptNAS) needs target-domain data during search, which external validation forbids. It also depends on a rotation-prediction task that is meaningless for rotation-invariant pathology patches. Probeable DARTS fixes the skip-connection collapse of one-shot search on pathology and evaluates transfer afterwards, with no hospital-split protocol. USAA searches augmentations and cells jointly on MedMNIST's internal splits. It notes that a smaller search space generalized better, a constraint we respect by keeping the space small.

None of these four compares greedy and global search under a reward that excludes external data. None measures the landscape that search actually faces.

The external-validation papers set the evaluation rules and the strongest competitor. WILDS shows that on Camelyon17 standard training drops from about 93% in-distribution to about 70% at a new hospital, and that robust objectives such as IRM and CORAL rarely beat standard training. Out-of-Distribution Robustness via Targeted Augmentations explains this: with few training hospitals, models memorize hospital-specific stain features. Stain-colour jitter lifts Camelyon17 external accuracy from 75.3% to 90.5%. That result is a real threat to any architectural story, and we treat it as such. The clinical studies, Ayaru et al. and Yao et al., supply the locked derivation-then-external protocol we copy: architecture, hyperparameters, and weights are frozen before the external cohort is touched.

Research Program

The core artifact is an exhaustively trained, hospital-split architecture landscape for Camelyon17-WILDS. We define a chain-structured macro space of four convolutional stages. Each stage chooses among six options combining kernel size, width, and whether to downsample or add a skip, giving 1,296 architectures. The space is deliberately small, which makes exhaustive training possible and follows USAA's observation that large spaces overfit small clinical data.

Every architecture is trained four times on patches from hospitals 1–3: once on all three, and once for each leave-one-hospital-out fold. We use a fixed, subsampled patch budget and a fixed schedule, all at small-network scale on 96×96 patches. A random 10% of architectures get two extra seeds to estimate the noise floor. Hospital 4 and hospital 5 are scored once per architecture, but those scores are written to a sealed file. No search procedure or selection rule may read them. Hospital 5 serves as the primary external cohort and hospital 4 as a second, independent one. This departs from the WILDS default of selecting on hospital 4, to match clinical practice.

On this table we compute, for both the in-hospital reward and $R(a)$, three quantities: the number of strict local optima under single-stage edits, the size of their basins of attraction, and the rank correlation with sealed hospital-5 accuracy. A local optimum counts only if it exceeds all neighbours by more than twice the seed standard deviation. This rules out the boring explanation that "ruggedness" is training noise.

We then run the search algorithms against the table as an oracle at matched evaluation budgets: greedy hill-climbing, progressive depth-first search with parent-beating pruning, random search, AOWS-style Viterbi decoding, and PVLL-style surrogate navigation. For Viterbi, unary and pairwise scores per stage are fitted from the evaluated samples. Because we know the global answer, we can say exactly how often each method's selected architecture lands in the top 1% of the space by sealed external accuracy.

To check that conclusions are not artifacts of oracle access, we repeat the main comparison with weight-sharing estimates. Here one supernet is trained per leave-one-out fold. As a second domain, we repeat the landscape study on iWildCam-WILDS, where camera locations play the role of hospitals, on a reduced space.

Baselines

The naive reference is a standard fixed backbone, ResNet-18 or DenseNet-121, trained on hospitals 1–3 with ordinary augmentation and selected by in-hospital validation. On WILDS, standard training reaches about 70% external accuracy on Camelyon17 per WILDS and 75.3% per Out-of-Distribution Robustness via Targeted Augmentations. We rerun it under our protocol instead of quoting it, because those numbers used hospital 4 for selection.

The strongest existing method is the same fixed backbone with targeted stain-colour jitter. That paper reports 90.5% average external accuracy on Camelyon17. We rerun it with the paper's augmentation settings and model selection restricted to hospitals 1–3, giving it the same GPU-hour budget as our full search for hyperparameter tuning. Beating it means a searched architecture, trained with the same stain jitter, has higher hospital-5 accuracy with non-overlapping seed confidence intervals and is no worse on hospital 4. If the searched network only matches the backbone at far fewer parameters, we report that as an efficiency result, not a robustness result.

The ablations that isolate the proposal's ingredients form a two-by-two grid: greedy versus Viterbi search, crossed with in-hospital versus leave-one-hospital-out reward, at identical evaluation budgets and training recipes. Random search under the leave-one-out reward at the same budget is the critical extra cell. SGAS-style sequential commitment is run as the strongest greedy representative. On iWildCam, the reference numbers are macro F1 of 33.3 for standard training and 36.5 with targeted augmentation, from the same targeted-augmentation paper.

Why not just…?

Why not just use a fixed backbone with stain augmentation? This is the most serious alternative. The 90.5% result suggests most of the Camelyon17 gap is a data problem, and the WILDS authors' remark that better architectures might help is a suggestion, not evidence. We therefore run every search arm both with and without stain jitter. If searched architectures gain over backbones only without jitter, the conclusion is that augmentation subsumes architecture on this shift, and we will say so. The secondary iWildCam study tests a shift where no single augmentation is known to be decisive.

Why not just swap the reward and keep greedy search? Changing greedy hill-climbing's reward to leave-one-hospital-out accuracy is cheap. If the cross-hospital landscape is no more rugged than the in-hospital one, it should work as well as anything else. The two-by-two grid answers this directly. The proposal's search-side claim survives only if the Viterbi-minus-greedy gap under $R(a)$ is clearly larger than under the in-hospital reward. Otherwise the recommendation is "greedy plus a transport-aware reward," which is itself a useful, simple finding.

Why not just run random search with leave-one-out selection? NASH found random search at 6–7% CIFAR-10 error against under 6% for its method. That is a modest gap. PVLL-NAS reports that surrogate navigation beats uniform sampling mainly at low budgets. Because our table covers the whole space, we can plot the probability of reaching the top 1% by external accuracy against budget for random, greedy, and global search. Random search wins if its curve matches the others at budgets practitioners would actually use.

Why not just do k-fold cross-validation within the pooled derivation hospitals? Pooled folds mix hospitals, so they measure reproducibility, not transportability. Yao et al. report an internal AUC of 0.90 falling to 0.86 externally. We include pooled 5-fold accuracy as a third reward and expect, but will test, that it ranks architectures by hospital-5 accuracy no better than plain validation.

Proposed Experiments and Decisive Checks

The first check is whether the leave-one-hospital-out reward rank-correlates with sealed hospital-5 and hospital-4 accuracy clearly better than in-hospital or pooled cross-validation accuracy. We compare the two Kendall τ values with bootstrap intervals across architectures. If it does not, the reward idea fails and the study reports a negative result.

The second check is whether the leave-one-out landscape has more noise-corrected local optima and smaller basins than the in-hospital landscape. This is the direct test that the trap is worse for transport.

The third check is the interaction in the two-by-two grid. A positive answer requires that global decoding beat greedy search on sealed external accuracy by more under the transport reward than under the in-hospital reward, measured over 20 search seeds. Separately, the progressive depth-first arm should show that pruned branches are over-represented among the architectures with the best external accuracy. That would quantify the premature-pruning concern from Flynn et al. in the transport setting.

The fourth check is the end-to-end comparison against stain-augmented backbones. Its pass and fail conditions are stated in the Baselines section, and it is repeated in reduced form on iWildCam.

Each outcome is informative alone. Together they say whether external-validation failure is partly a search failure, or purely a reward-and-data failure that architecture search should stay out of.