Video reconstruction networks recover a full video from a few compressed or corrupted measurements. Choosing their architecture is expensive, because the only reliable way to tell which design is better is to train each candidate to convergence. The usual shortcut is to train each candidate briefly and rank by early error. We argue this shortcut is systematically misleading for reconstruction, and that the fix comes from spatio-temporal regularization. Neural networks fit coarse, slowly varying structure first and fine detail later. Early in training, the total error is therefore dominated by low spatial and temporal frequencies, which every reasonable architecture eventually fixes. What separates good architectures from mediocre ones is how well they recover fine texture and fast motion. These are the high-frequency bands that total variation penalties and their high-order variants were designed to protect, and they converge last.
The proposal is to split each candidate's early learning curve into bands of spatial and temporal frequency, extrapolate each band separately, and rank architectures by the predicted final error summed over bands. Two pieces get built around this. The first is a small exhaustively trained benchmark of unrolled video compressive-sensing networks, whose per-stage building blocks range from learned 3D total-variation steps to 2D, factorized, and full 3D convolutions. The second is a test of whether band-resolved extrapolation beats the cheap estimators the architecture-search literature already uses. Those estimators have been validated almost entirely on 2D image classification.
Core Claim
The total-error learning curve of a reconstruction network is a sum of per-band curves that run on very different timescales. Extrapolating that sum from a short prefix overweights the fast bands, so architectures get ranked mostly by how quickly they learn coarse structure. Extrapolating each band on its own removes this bias. At an equal training budget, it should improve rank correlation with fully trained quality, and it should help most among the top architectures, where existing cheap estimators fail (EZNAS; NAS-Bench-Suite-Zero).
Concretely, let $x$ be a ground-truth video clip and $\hat{x}_s$ the network's reconstruction after $s$ training steps. Let $P_b$ project onto band $b$ of the 3D Fourier transform, where bands are defined jointly by spatial radius and temporal frequency. The band error is
$$e_b(s) = \frac{\lVert P_b(\hat{x}_s - x)\rVert^2}{\lVert P_b x\rVert^2}.$$
We fit $e_b(s) \approx a_b s^{-\gamma_b} + c_b$ on the first $k$ steps. Here $a_b$ is the initial excess error, $\gamma_b$ the decay rate, and $c_b$ the asymptote. We then predict final mean-squared error as $\sum_b \lVert P_b x\rVert^2 \, \hat{c}_b$. Power laws are the standard empirical form for learning curves. The point here is only that each band gets its own exponent.
Why This Intersection, and What Is Already Done
Classical spatio-temporal regularization already encodes the relevant structure. Hosseini and Plataniotis show that standard first-order total variation, the penalty on differences between neighboring pixels and frames, attenuates high-frequency texture. They replace it with high-order filters, which recover substantially more detail on Hall-Monitor. Imaizumi and Hayashi identify the converse risk: smoothness priors blur sharp boundaries. Both papers motivate the proposal by placing the hard part of the problem in the high bands. Our use of their insight is diagnostic rather than as a penalty: the frequency decomposition they reason about becomes the measuring instrument for architecture quality.
On the search-cost side, three lines of work supply methods and constraints. Zero-cost proxies score untrained networks with one forward/backward pass. EZNAS evolves such scores and reaches Kendall tau 0.65 on NAS-Bench-201 CIFAR-10. NAS-Bench-Suite-Zero shows that ensembling proxies helps and that single proxies are biased toward large models. Both are confined to classification. Budgeted performance estimation (Zheng et al., CVPR 2020) finds that training epochs dominate ranking fidelity while input resolution can be cut aggressively. It also reports that cheap estimates keep local but lose global correlation with converged performance. That loss of global correlation is exactly the failure our mechanism targets, and their finding that resolution can be cut is one we must check for reconstruction, since downsampling deletes the very bands we care about. Saxe et al. show that architecture alone fixes a network's frequency selectivity even with random weights. This constrains the design: some band behavior is visible at initialization, so a zero-cost spectral score is a necessary baseline.
The closest connecting work does not do this. AutoSTF cuts search cost 13.48x for traffic forecasting by searching temporal and then spatial modules separately. It addresses forecasting rather than inverse problems, and it uses no frequency-aware estimator. We borrow its separation of spatial and temporal operator choices for our search space. EMR-NAS applies differentiable search to static 2D MRI reconstruction at about 0.5 GPU days per fold. Shin et al. search filter shapes on driving video for steering regression, not reconstruction. The unrolled video network of Zheng et al. (Two-Stage is Enough) was designed by hand. Unrolling turns the iterations of a regularized solver into network stages. None of these works study how cheap estimates rank reconstruction architectures, and none decompose the estimate by frequency.
Research Program
Search space. The first step is a search space built on the two-stage unrolled structure of Zheng et al., with the number of stages extended to between one and four. Each stage keeps the physics-derived data-consistency step and the reference measurement frame. Each stage's learned prior block is chosen from five options: a learned 3D total-variation proximal layer with trainable high-order difference filters, in the spirit of Hosseini and Plataniotis; a 2D spatial CNN; a factorized spatial-then-temporal CNN; a full 3D CNN; and a temporal low-rank projection followed by a spatial CNN, echoing the Tucker-style separation in Shen et al.. Width and depth also vary per stage. Mixing explicit regularizers with learned blocks lets the benchmark ask whether early stages prefer smoothing priors and later stages prefer detail-preserving ones, which is an open question in its own right.
Benchmark. We sample roughly 300 architectures stratified across this space. Each is trained to convergence with a fixed recipe on DAVIS 2017 clips under simulated coded-aperture masks at 8:1 temporal compression. Each is evaluated on the grayscale benchmark used by Zheng et al., with Hall-Monitor and Container added as out-of-distribution checks. Every checkpoint stores band-resolved error curves, so any estimator can later be replayed at any budget without retraining. Releasing this as a tabular benchmark is a contribution independent of the main claim.
Premise checks. Before testing estimators, we verify two premises. The first is that bands converge on measurably different timescales, which shows up as separated fitted exponents $\gamma_b$. The second is that the variance of converged PSNR across architectures sits disproportionately in the high-frequency spatio-temporal bands, especially among the top decile. If either premise fails, the mechanism has nothing to exploit.
Estimators. Finally we compare estimators at matched budgets of $k$ steps, from 1% to 10% of full training. A secondary task, video completion with 90% missing pixels on Candela, tests whether the effect carries beyond compressive sensing.
Baselines
The naive reference point is parameter count, together with FLOPs. NAS-Bench-Suite-Zero shows these are surprisingly competitive on classification but biased toward large models. In our space, large full-3D blocks are not always best, so this baseline tests whether our estimator captures anything beyond size. Beating it means a higher Kendall tau overall and a lower top-k regret, defined as the PSNR gap between the selected architecture and the benchmark's best.
The second baseline family is zero-cost proxies: grad_norm, snip, synflow, nwot, and an XGBoost ensemble of all of them, as in NAS-Bench-Suite-Zero. Each is recomputed with the reconstruction loss in place of cross-entropy. We also add a zero-cost spectral score: the band-wise Jacobian response of the untrained network to noise. This is our own control, motivated by Saxe et al.. The ensemble gets a calibration set of the same size as any calibration our method uses. The best figure in the file for such proxies is Kendall tau 0.65 for EZNAS-A on NAS-Bench-201 CIFAR-10 (EZNAS). We found no reported result on Lacuna for zero-cost proxy rank correlation on any video reconstruction task, so the comparison has to be measured here.
The strongest competitor is budgeted short training, ranked by validation PSNR at step $k$. Its fidelity settings (epochs, crop resolution, number of stages trained) are tuned by Minimum Importance Pruning as in Zheng et al. (CVPR 2020). That paper reports reducing CIFAR-10 search to 0.33 GPU days at 2.66% test error. We found no reported result on Lacuna for budgeted estimation on video reconstruction. This baseline receives the same GPU-hours as our method, including MIP's own tuning cost.
The ablation that isolates our key ingredient is power-law extrapolation of the total error curve under the identical fitting procedure and budget, with no band split. A further ablation weights only high bands without extrapolating, and another uses only low bands. Beating total-curve extrapolation at the same $k$, with a non-overlapping bootstrap confidence interval on top-decile Kendall tau, is the result that would support the claim.
For end-task context, we report the PSNR of the architecture each estimator selects, against the hand-designed two-stage network, which reports 35.63 dB average PSNR on the grayscale benchmark (Zheng et al.). We retrain that network under our recipe for a fair comparison. We also report the search cost of an EMR-NAS-style differentiable search over the same space (EMR-NAS reports about 0.5 GPU days per fold on 2D MRI).
Why not just…?
Why not just train each candidate briefly and rank by early PSNR? This is the real threat, and BPE shows it works well for classification. Our argument is specific: early PSNR mixes bands that converge at different times, so it ranks candidates by speed on coarse structure. The matched-budget comparison settles the question directly. If short training ties our estimator at every $k$, the band split adds nothing, and we will report that. There is one place we expect a clear difference. MIP's recommendation to shrink input resolution may actively hurt here, because downsampling discards the high bands, and the benchmark lets us measure this.
Why not just extrapolate the total learning curve? This is the closest alternative and is run as our core ablation. A sum of power laws with different exponents is not itself well fit by a single power law at short horizons, which is the reason we expect the per-band fit to win. Whether that matters in practice is exactly what the ablation shows.
Why not just use zero-cost proxies with a reconstruction loss? They are the cheapest option and may separate broken architectures from working ones. However, both EZNAS and NAS-Bench-Suite-Zero report that they fail to rank the top 10% of architectures, and the top of the ranking is where search decisions are made. Our zero-cost spectral control tests the strongest version of this idea. If it matches our estimator, then architecture alone determines band behavior, as Saxe et al. would predict, and a cheaper method should replace ours.
Why not just use the hand-designed two-stage network, or a classical 3D total-variation solver? Classical solvers need no search, but they are reported to be about 17 times slower than unrolled networks on color video (Zheng et al.) and cap texture fidelity. The hand-designed network is a strong point, and it is included in the benchmark. If no searched architecture beats it by a meaningful margin, the conclusion is that search is not worth paying for on this task, and the benchmark will show that honestly.
Decisive Checks
The proposal stands or falls on three measurements. The first is whether fitted band exponents differ across bands and whether variance in converged quality concentrates in high bands. The second is whether, at 2–5% of full training, band-resolved extrapolation exceeds total-curve extrapolation and MIP-tuned short training on top-decile Kendall tau and on top-5 regret on the grayscale benchmark. The third is whether the advantage persists on Candela completion and on Hall-Monitor and Container. A positive result would give reconstruction-specific architecture search a cheap, principled estimator. A negative result on the first measurement would show that spectral bias does not separate architectures here, which would itself be informative for anyone extending classification-derived search shortcuts to inverse problems.
References
- EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- High-Accuracy Total Variation With Application to Compressed Video Sensing
- Tensor Decomposition with Smoothness
- Rethinking Performance Estimation in Neural Architecture Search
- On Random Weights and Unsupervised Feature Learning
- AutoSTF: Decoupled Neural Architecture Search for Cost-Effective Automated Spatio-Temporal Forecasting
- Enhanced MRI Reconstruction Network Using Neural Architecture Search
- Differentiable Neural Network Architecture Search
- Two-Stage is Enough: A Concise Deep Unfolding Reconstruction Network for Flexible Video Compressive Sensing
- Smooth Robust Tensor Completion for Background/Foreground Separation with Missing Pixels: Novel Algorithm with Convergence Guarantee