How Much Access Does Temporal Smoothing Need? An Oracle Separation for Video Parameter Jitter

Many video systems estimate a small set of parameters for every frame and then render from them. Examples include camera rectification, the viewing direction for a 360° video, and the strength settings of color filters. When each frame is solved on its own, the estimate often jumps between two nearly equally good answers, and the output flickers. Practitioners fix this in one of two ways. The cheap fix smooths the sequence of per-frame answers after the fact, for example with an exponential moving average (a running weighted average of past estimates). The expensive fix re-solves each frame with a penalty for moving far from the previous frame's parameters. This note argues that the gap between the two fixes is a question of access, not of tuning. A smoother that only sees each frame's best answer cannot, in principle, tell a real scene change from a tie between two answers. A smoother allowed to evaluate the frame's objective at a handful of chosen points can tell them apart.

We make this precise using the main proof tool from oracle complexity theory: build two worlds that look identical through a restricted interface but require different correct behavior. The theory predicts a method that sits between the cheap and expensive fixes. Each frame, it spends a few evaluations of the objective on a short candidate list, and that should be enough to reproduce the penalized solution. We then test whether this holds on real pipelines.

Core Claim

Let $L_t(\theta)$ be the per-frame objective over parameters $\theta$. The temporally regularized path is

$$\theta^\lambda_t = \arg\min_\theta \; L_t(\theta) + \lambda \,\|\theta - \theta^\lambda_{t-1}\|,$$

where $\lambda$ trades frame fidelity against smoothness. This is the template used in stereo rectification (Cheng et al.) and in 360° projection (Kim et al.). We consider three access levels. An argmin oracle returns only $\theta^*_t = \arg\min L_t$. A q-query value oracle returns $L_t$ at $q$ points the smoother chooses. Full access allows re-optimization.

The first claim is a separation. For any causal smoother that sees only argmin answers, there are two objective sequences with identical argmin answers on every frame whose regularized paths differ by a mode gap $\Delta$ from some frame onward. Every such smoother therefore has worst-case error at least $\Delta/2$, whatever its filter design or memory.

The second claim is an upper bound. If the objective has at most $K$ well-separated near-optimal basins, $q = O(K)$ value queries per frame recover $\theta^\lambda_t$ exactly. The queries go to the previous solution, propagated forward, and to the current per-frame answers.

The third claim is a matching lower bound of $\Omega(K)$ queries. It uses a stage-by-stage adversary that answers each query and keeps any unqueried basin free to become the true minimum. This is the string-by-string diagonalization used in oracle constructions such as Rothe's immunity separations, with the oracle's unqueried strings replaced by unqueried basins.

To be clear about scope: this does not advance structural complexity theory. It borrows its method, which is indistinguishability arguments against a restricted query interface, to settle an engineering question that the video literature has only answered empirically.

Relation to Prior Work

Two papers motivate the proposal. Harmonizer predicts arguments for six physical filters and removes flicker with an exponential moving average over those arguments, running at 56 FPS on 1080p video with a 21.7 MB model. Its smoother is exactly an argmin-oracle smoother, so our lower bound applies to it directly. Wang and Oh sit at the other extreme: they update parameters by gradient descent at test time under temporal consistency constraints. They report that this costs throughput and drifts under noisy pseudo-labels. Our query-based smoother aims for the second method's mode consistency at close to the first method's cost.

Two lines of work constrain the design. Penalties over a whole window of frames, as in Multi-Cali Anything, avoid the causal problem by using future frames, so they are a non-causal reference rather than a competitor. EXTERN adapts video classifiers when the source model is reachable only through a prediction API. It is the realistic instance of black-box access, and our theory gives it a formal counterpart: label-only APIs fall under the argmin lower bound, while APIs that return scores give value queries.

On the theory side, Aaronson's "Oracles Are Subtle But Not Malicious" and Barak, Lindell and Vadhan supply the conceptual contrast between black-box and non-black-box access. Aaronson's "war of attrition", in which the oracle is adjusted step by step against a progress measure, is the closest model for our adaptive adversary. None of these papers treats sequential parameter estimation.

Research Program

The theoretical part proves the three claims in a stylized model. Each objective $L_t$ is a minimum over $K$ basins with drifting centers and depths, plus bounded noise. The argmin construction is short: take one sequence where the deeper basin alternates because of noise, and another where it truly switches. Both produce the same argmin answers, but only in the second does the regularized path switch. The query lower bound needs care, because the adversary must stay consistent with the Lipschitz and drift assumptions while it delays committing to a basin. We will also characterize when $O(K)$ queries suffice under imperfect basin separation. The expected result is error that scales with noise amplitude divided by $\lambda$. That form follows from the fact that a basin switch happens only when the depth gap exceeds $\lambda$ times the distance between basins.

The algorithmic part builds the query-augmented smoother. Each frame, it forms a candidate set from the previous solution and the top-$K$ per-frame predictions. It evaluates the objective plus the penalty on each candidate and refines the winner with a few local steps. For learned regressors without a ground-truth test-time loss, we use the self-supervised objective the pipeline already exposes. For harmonization this is a foreground–background statistics match; for rectification it is epipolar residual on tracked features.

Baselines

The do-nothing reference is per-frame estimation with no smoothing, which sets the level of jitter.

The strongest cheap competitor is an exponential moving average on parameters, as in Harmonizer. We extend it with an adaptive-cutoff variant and a causal median filter. All three get the same tuning budget, a grid search over smoothing constants on held-out sequences, that our method gets for $\lambda$ and $K$.

The strongest expensive competitor is full regularized re-optimization of the objective above, run to convergence with multiple restarts. It defines the accuracy ceiling. In the segmentation setting we add test-time gradient adaptation in the style of Wang and Oh.

Two ablations isolate the key ingredient, which is choosing candidates from both the previous solution and the current modes. The first draws the same number of queries at random. The second queries only the previous solution, which amounts to warm-starting.

Beating the baselines means two things. Our method must cut flicker below the moving average at equal fidelity on mode-switching sequences. It must also come within a few percent of full re-optimization's error while using at least an order of magnitude fewer objective evaluations.

No reported flicker or temporal-error result was found on Lacuna for Harmonizer or for the other pipelines. The only reported figure for the strongest cheap baseline is Harmonizer's 56 FPS at 1080p, which we use as the throughput target.

Why not just…?

Why not just tune the moving average or use a better causal filter? The separation theorem says no causal function of the argmin sequence avoids $\Delta/2$ error on the adversarial pair. Tuning only moves the failure between lag and blending two basins into an invalid intermediate setting. The synthetic experiments construct exactly this pair and plot the error of every tuned filter against the bound.

Why not just warm-start a local solver from the previous frame? This is the real threat. Warm-starting gives mode persistence almost for free, using one query. Our theory predicts it fails the other way: it stays in a stale basin after a genuine scene change, because it never inspects the alternative. The previous-solution-only ablation measures this directly. If warm-starting matches our method on real footage, that tells us real videos rarely contain genuine basin switches, and we will report it as such.

Why not smooth the rendered pixels instead of parameters? Pixel-space averaging sees even less than the argmin oracle and blurs content. We include it as a baseline, but the lower bound applies to it all the more.

Proposed Experiments

The decisive check is synthetic. We use families with $K \in \{2, 4, 8\}$ basins, controlled noise, and planted true switches. Here we can verify the $\Omega(K)$ query curve and the $\Delta/2$ floor for argmin smoothers exactly.

The real-pipeline checks are threefold. First, Harmonizer run on video sequences built from iHarmony4 composites with compression and lighting perturbations. Second, the uncalibrated stereo rectification setting of Cheng et al.. Third, the black-box adaptation setting of EXTERN on UCF-HMDB and Sports-DA, comparing label-only API access with score-returning API access. No public video benchmark for the rectification or projection tasks is listed in the file, so we will record and release sequences with planted switch events.

The metrics are frame-to-frame parameter variation and temporal warping error for flicker, per-frame fidelity, switch-detection latency, objective evaluations per frame, and frames per second. The decisive outcome is the predicted ordering: argmin smoothers sit at the theoretical floor, warm-starting lags on true switches, and the query-augmented smoother tracks full re-optimization at a small multiple of the moving average's cost.