Many generative models turn an observation into a compact code, the latent, with a single pass of an encoder network. Recent work shows that a few extra steps of instance-specific optimization, starting from the encoder's output, give noticeably better codes. This is called iterative latent refinement. The field has used the encoder as a "warm start" without ever checking the premise that makes warm starts work: that the starting point sits inside a region where local optimization behaves well. In the optimization literature this region is called a basin of attraction. Inside it, gradient steps converge quickly and reliably. Outside it, they stall on flat plateaus, drift toward worse local optima, or diverge.
We propose to measure that premise directly, per instance, and act on it. Within a few steps of refinement we want to tell whether a given encoder output is inside a well-behaved basin, using only a handful of extra gradient and curvature probes. We then spend refinement compute accordingly. Instances that are certified as inside the basin get a fast local solver and an early stop. Instances that are not certified get more steps or an alternative starting point. The scientific bet is that certification fails in a predictable way when inputs drift away from the training distribution. That is exactly where amortized encoders are known to degrade, and where fixed-budget refinement quietly wastes compute or fails.
Core Claim
The benefit of refining from an encoder output is governed by whether that output lies in a region where the per-instance latent objective $L_x(z)$ satisfies a local gradient-domination (Polyak–Łojasiewicz) condition,
$$\|\nabla L_x(z)\|^2 \;\ge\; 2\mu_x\,\big(L_x(z) - L_x^\star\big),$$
where $z$ is the latent, $L_x^\star$ is the best value reachable nearby, and $\mu_x > 0$ is a local constant. When this holds along the trajectory, gradient descent converges geometrically at a rate set by $\mu_x/\beta_x$, where $\beta_x$ is the local smoothness. This is the standard consequence of the inequality, and it is why a geometric fit to the first few steps can predict the remaining gap.
We make three claims. First, on in-distribution data, most encoder outputs satisfy this condition with a usable $\mu_x$. Second, the fraction that does drops sharply under distribution shift and at extreme operating points such as very low bitrates. Third, a cheap online estimate of the condition predicts refinement success well enough to reallocate a fixed compute budget and beat uniform-step refinement at matched cost. The first two claims are empirical science the field lacks. The third is the method.
Relation to Prior Work
The motivating evidence comes from four sources. Improving Inference for Neural Image Compression runs gradient refinement from a compression encoder's output. It uses stochastic Gumbel annealing to handle integer latents and reports 15% bitrate savings on Kodak and 20% on Tecnick. The authors argue that the encoder places latents in "the right neighborhood" but never test when it does not. Semi-Amortized Variational Autoencoders trains the encoder end-to-end through ten gradient steps on the variational objective, and needs gradient clipping to stay stable. That need is itself a hint that some starts fall outside a benign region. Iterative Amortized Inference replaces hand-designed updates with a learned update network and treats the landscape as a black box. Inference Suboptimality in Variational Autoencoders shows two things: the amortization gap dominates on complex data (about 37.47 nats on 3-bit CIFAR), and encoders generalize their inference poorly to test data. This is the mechanism by which we expect basin membership to erode.
All four methods run a fixed number of refinement steps for every instance, and none asks whether the start is inside a basin. Our proposal differs in three ways. It measures membership, allocates steps per instance, and switches solvers based on that measurement.
Several papers supply the method. Fast Stochastic Algorithms for SVD and PCA shows that for principal component analysis, a single good initialization step lands iterates in a locally strongly convex region, while random starts sit on flat terrain. PhaseMax shows that a spectral start cuts phase-retrieval sample complexity from $O(n^{1.5})$ to $O(n)$. Together they supply the conceptual template: warm start, certify, then run a fast local method. IQN proves superlinear local convergence for incremental quasi-Newton methods only once iterates are near the optimum. We reuse this as the solver we switch to after certification.
Learning to Warm-Start Fixed-Point Optimization Algorithms trains initializers by unrolling solver steps, but it works on convex problems and names non-convex landscapes as open. We do not propose a new way to train the initializer. We ask when a trained initializer's output can be trusted, and what to do when it cannot.
Two further papers bound our claims. The predictive-coding analysis in Only Strict Saddles in the Energy Landscape of Predictive Coding Networks? characterizes the weight landscape only after the inner latent inference has fully converged. It explicitly leaves open how inner inference depends on its starting state. We treat this as a later extension rather than a core testbed, because its guarantees assume the converged regime we are questioning. Finally, bounds for bi-factored low-rank gradient descent (Finding Low-rank Solutions to Matrix Problems) warn that basin radius shrinks under ill-conditioning. We therefore expect certification to be hardest exactly where the latent posterior is poorly conditioned, and we test for that.
Research Program
The first component is an offline basin atlas. For a trained model and each test instance $x$, we compute a reference optimum $\hat z^\star(x)$ by long refinement: hundreds of steps from the encoder output, plus several perturbed and prior-sampled restarts. We call an encoder start "in-basin" if refinement from it reaches the best restart's objective within tolerance in a modest budget.
Along the trajectory we record four quantities. The first is the empirical gradient-domination ratio $\|\nabla L_x\|^2 / (2(L_x - L_x^\star))$. The second is the smallest Hessian eigenvalue, estimated with Lanczos iterations built on Hessian-vector products. The third is the basin radius, measured by shrinking random perturbations of the start until convergence to $\hat z^\star$ is preserved.
From these we produce a map of basin membership as a function of three factors: distribution shift, operating point (the rate-distortion trade-off weight, or the KL weight), and decoder depth. This directly answers the open questions the file identifies about latent-space geometry and generalization mismatch.
The second component is an online certificate. The atlas uses unknown optima, so it cannot be deployed. The deployable certificate uses only the first $j$ refinement steps, with $j$ between 2 and 4. It combines two signals. The first is the contraction ratio of successive gradient norms, which under the inequality above is roughly constant and below one. The second is a two- or three-iteration Lanczos estimate of local minimum curvature, which flags nearby negative-curvature or flat directions.
A small logistic model, fit on the atlas labels from training data only, maps these features to a probability that the instance is in-basin. The certificate adds $O(j)$ gradient evaluations and a few Hessian-vector products.
The third component is a certificate-driven refinement policy under a fixed average compute budget. For certified instances, we switch to a limited-memory quasi-Newton update and stop once the certified geometric fit predicts the remaining gap is below tolerance. For uncertified instances, we spend the saved budget on continued first-order refinement, a small number of restarts from perturbed encoder outputs, or both, keeping whichever reaches the best objective.
In image compression, the discrete-latent annealing of Bamler et al. is kept intact. Certification is applied to the continuous relaxation before annealing. We test separately whether the annealing schedule interacts with basin membership.
Baselines
The naive reference point is the encoder alone, with no refinement. This is the standard amortized model: the hyperprior compression codec on Kodak and Tecnick, and the standard VAE on MNIST, Omniglot, Fashion-MNIST and Yahoo. On Yahoo, SA-VAE reports the standard VAE at perplexity 62.5 with a collapsed KL of 0.01. Any refinement policy must clearly beat this reference, and it tells us how much headroom exists.
The strongest existing competitor is uniform fixed-step refinement from the encoder output. In compression this is the stochastic Gumbel annealing procedure of Improving Inference for Neural Image Compression, which reports an average 15% bitrate saving on Kodak and 20% on Tecnick over the base model. In VAEs it is SA-VAE, which reports perplexity 60.4 with KL 7.19 on Yahoo. We also include Iterative Amortized Inference, which reports perplexity 285.0 against 323.0 for the standard amortized model on RCV1.
We re-run these methods ourselves on identical trained models, with the same decoder and the same average number of gradient evaluations per instance as our policy, certificate cost included. Step size and number of steps get the same tuning budget on a held-out split. Beating them means one of two things. Either we get a better average objective (BD-rate, or the evidence lower bound, the ELBO) at equal compute, or we get equal objective at meaningfully lower compute. A win must hold on the tail as well as on average: the worst decile of instances by final objective should improve.
The key ablation isolates the certificate. We keep the same compute reallocation machinery but allocate steps using a random score, and separately using a score based only on the raw loss trajectory. The second variant tests whether our curvature and gradient-domination features add anything over simply watching the loss go down. A second ablation removes the quasi-Newton switch, using first-order steps everywhere. This tells us whether gains come from better allocation or from the faster local solver.
Why not just…?
Why not just use a bigger encoder? Cremer et al. (Inference Suboptimality) find that the amortization gap persists on complex data and that encoders overfit the inference demands of the training set. More capacity plausibly worsens that overfitting under shift. Bamler et al. obtain their gains with an unchanged model. We nonetheless include a larger-encoder variant at matched test-time compute. If it matches our policy on shifted data, the basin story is unnecessary.
Why not just stop when the loss stops decreasing? This is the most serious threat. A plateau detector is cheap and might capture most of what the certificate captures. Our loss-only ablation exists precisely to settle this. If loss-only allocation matches the curvature-based certificate, we will report that the practical method reduces to adaptive early stopping. The basin atlas would then remain as the scientific contribution. We expect the curvature probe to matter specifically for instances sitting on flat regions or near saddles, where the loss decreases slowly but steadily. Plateau rules misread such instances as converging.
Why not just refine longer, or restart from several points, for everyone? Uniform long refinement is an upper-bound baseline in our atlas, not a competitor at matched compute. Pure cold-start optimization is already known to be weak: SA-VAE reports that stochastic variational inference from scratch with 80 steps falls short of 10 warm-started steps. The open question is whether uniformly distributed restarts at matched budget rival targeted ones. We test uniform restarts directly.
Why not use normalizing flows? Normalizing flows are posterior families built from invertible transformations. They enlarge the family of posteriors the model can represent, which addresses the approximation gap. Our question concerns optimization from a starting point, which flows do not remove: Cremer et al. still measure a 12.86-nat amortization gap on MNIST with a flow posterior. The two approaches are complementary, and we leave combining them to follow-up work.
Proposed Experiments
For compression, we train the hyperprior codec on OpenImages V7 across a range of rate-distortion weights. We evaluate on Kodak, Tecnick and the CLIC 2024 validation set, holding out the extreme rate settings as an operating-point shift.
For VAEs, we train on MNIST and evaluate on MNIST, Fashion-MNIST and Omniglot as increasing shift. We use Yahoo and RCV1 to test text, where the posterior-collapse regime may create very flat latent landscapes. We found no reported result on Lacuna for refinement-from-encoder under these cross-dataset shifts, so the atlas numbers will be new.
Metrics fall into three groups. The first is the objective: BD-rate on PSNR and MS-SSIM for compression, the ELBO and importance-weighted likelihood for VAEs, and perplexity for text. The second is compute, measured as gradient evaluations and wall-clock time per instance. The third is certificate quality: the area under the ROC curve (AUROC) for predicting in-basin status, plus calibration.
Three checks decide the outcome. First, the in-basin fraction must fall measurably with shift and at extreme rates. If it does not, the premise fails. Second, the online certificate must predict atlas labels on shifted data it was never fit on with an AUROC well above the loss-only predictor. Third, the certificate-driven policy must beat uniform refinement at matched compute on the worst-decile instances under shift. A null result on the third check alone would still yield a published map of when amortized warm starts can be trusted. A null result on the second check would tell practitioners that watching the loss is enough.
References
- Improving Inference for Neural Image Compression
- Semi-Amortized Variational Autoencoders
- Iterative Amortized Inference
- Inference Suboptimality in Variational Autoencoders
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
- PhaseMax: Convex Phase Retrieval via Basis Pursuit
- IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate
- Learning to Warm-Start Fixed-Point Optimization Algorithms
- Only Strict Saddles in the Energy Landscape of Predictive Coding Networks?
- Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably