Well-Conditioned Input Convex Networks for Certified Implicit Gradients

Many learning systems contain an inner optimization problem. Examples include computing an optimal transport map, inverting a flow, completing an image by minimizing a learned energy, or picking an action that minimizes a learned cost. Training the outer model requires gradients through the inner problem's solution. Input convex neural networks (ICNNs) are networks constrained so that their output is a convex function of their input. They make that inner problem convex, so its minimizer is unique. Implicit differentiation obtains the minimizer's gradient from the optimality condition at the solution, by solving one linear system with the Hessian, instead of backpropagating through every solver step.

In principle the two fit together well: convexity makes the Hessian invertible, and implicit differentiation needs an invertible Hessian. In practice ICNNs are reported to be "stiff." Inner solves converge slowly and convex potentials lose to unconstrained networks on transport benchmarks. This proposal argues that the missing ingredient is control over curvature in both directions, not convexity alone. We propose an ICNN whose Hessian is guaranteed to lie between a lower bound $\mu$ and an upper bound $L$. Those two numbers then set, in advance and with a certificate, how many inner-solver and linear-solver iterations are needed for a gradient of a requested accuracy.

Core Claim

Write the inner problem as $x^*(y)=\arg\min_x\,[f_\theta(x)-\langle x,y\rangle]$. Here $f_\theta$ is the ICNN potential with parameters $\theta$, and $y$ is the query point; this is exactly the convex-conjugate problem in neural optimal transport and flow inversion. The implicit function theorem gives $\partial x^*/\partial y = [\nabla^2 f_\theta(x^*)]^{-1}$. A conjugate-gradient solve of this system needs on the order of $\sqrt{\kappa}\log(1/\epsilon)$ Hessian-vector products, where $\kappa=L/\mu$ is the Hessian's condition number; this is the standard conjugate-gradient rate.

If the architecture guarantees $\mu I \preceq \nabla^2 f_\theta \preceq L I$ everywhere, every quantity in the backward pass becomes certifiable from things measured at run time. For an approximate inner solution $\hat x$, strong convexity gives

$$\|\hat x - x^*\| \le \frac{\|\nabla f_\theta(\hat x) - y\|}{\mu},$$

so the observed gradient residual bounds the distance to the true minimizer. Combined with a bound $M$ on how fast the Hessian changes (a third-derivative bound that also comes from the activations), the error of the implicit Jacobian computed at $\hat x$ is at most $M\|\hat x-x^*\|/\mu^2$, plus the known conjugate-gradient error.

The empirical claim we will test is sharper and falsifiable. The stiffness and benchmark gap of ICNNs documented in prior work is driven mainly by an unbounded condition number, not by a lack of expressivity. If that is right, sweeping $\kappa$ should trace a curve on which a bounded-$\kappa$ ICNN matches non-convex potentials on transport accuracy while keeping a unique minimizer and certified gradients.

What Exists and What Is Missing

Several papers supply the method. The original Input Convex Neural Networks paper introduced fully and partially convex architectures, built from non-negative hidden weights, convex non-decreasing activations, and unconstrained skip connections from the input. It already differentiated through the inner minimizer via its optimality conditions. It did not control curvature, and it trained only on small benchmarks. Convex Potential Flows adds a quadratic term so the potential is strongly convex. It inverts flows with L-BFGS and backpropagates through the inversion using conjugate gradient on Hessian-vector products. Its strong convexity is a lower bound only, and it reports that capacity required hand-engineered input augmentation. Efficient and Modular Implicit Differentiation proves that the implicit Jacobian's error is of the same order as the inner solver's error. We make the constants in that bound explicit and architecturally controlled, which turns an asymptotic statement into a stopping rule.

Two papers motivate the work by documenting the gap. On amortizing convex conjugates for optimal transport shows that a predict-then-refine scheme, an amortized guess followed by GPU L-BFGS, improves the continuous Wasserstein-2 benchmark substantially. It also finds that non-convex MLP potentials often beat ICNNs despite having no guarantees, and attributes the ICNN problem to optimization stiffness. Do Neural Optimal Transport Solvers Work? built that benchmark and found many solvers above 70% unexplained variance in 64 dimensions. If our hypothesis is correct, stiffness is a conditioning phenomenon, and conditioning can be designed.

Another paper constrains the design. Wasserstein-2 Generative Networks shows that ReLU potentials give piecewise-constant gradients that tear densities, and it uses smooth activations instead. A ReLU ICNN has a Hessian that is zero almost everywhere, so $\mu>0$ must come from an explicit quadratic term and $L<\infty$ from smooth activations. Maxout ICNNs as in Learning with Stochastic Orders are therefore outside our certified class. We treat them as a reference point.

Two other intersection papers, Fast and Reliable N-k Contingency Screening and Locally Convex Global Loss Network, pair ICNNs with differentiable optimization in power-system screening and decision-focused learning. Neither addresses solver conditioning or gradient certification.

Research Program

Architecture. The first piece is a two-sided curvature-bounded ICNN: $f_\theta(x)=\tfrac{\mu}{2}\|x\|^2+g_\theta(x)$. Here $g_\theta$ is an ICNN with activations whose second and third derivatives are bounded, such as softplus. For each layer we derive a recursive bound on the operator norm of $g_\theta$'s Hessian in terms of the weight norms and the activation-curvature constants. We then rescale the weights at every step, analogous to spectral normalization, so that the bound equals a chosen $L-\mu$. The constructive step that needs checking is tightness. A loose bound would over-shrink the network, so we will compare the certified $L$ against Lanczos estimates of the true largest Hessian eigenvalue on trained models. If the ratio is large, we will move to a per-block bound or a learned diagonal preconditioner.

Solver. The second piece is a certified implicit layer. The forward pass runs L-BFGS, optionally warm-started by an amortized predictor as in the predict-then-refine method. It stops when the residual bound above guarantees a target distance to the minimizer. The backward pass runs conjugate gradient for exactly the number of steps implied by $\kappa$ and the target Jacobian accuracy, preconditioned with the known $\mu$ and $L$. The same certificate also covers envelope-theorem gradients: their bias is controlled by $\|\hat x - x^*\|$ through the same inequality. The layer therefore serves both the transport dual, where an envelope gradient suffices, and tasks where the full Jacobian $\partial x^*/\partial(\cdot)$ is required.

Analysis. The third piece is an empirical analysis of conditioning in existing ICNN potentials. On the benchmark pairs, we will measure the Hessian spectra of ICNN potentials trained with existing recipes. We then correlate condition number with inner-solve iteration counts, the fraction of solves that miss tolerance, and final transport accuracy. This tests the core hypothesis before any new architecture enters.

Baselines

The naive reference point is a vanilla ICNN trained with weight clipping, as in Input Convex Neural Networks, with conjugates computed by L-BFGS run to a fixed iteration count and gradients taken at whatever point the solver reaches. It shows what convexity alone buys, and it is the configuration our hypothesis says is ill-conditioned.

The strongest existing method on the transport question is the predict-then-refine conjugate solver of On amortizing convex conjugates for optimal transport, run with both its non-convex MLP potential and its ICNN potential. The file reports that it improves $L^2$-UVP (unexplained variance of the map, where 0% is exact) by a factor of 1.8x to 4.4x over prior best results on the Wasserstein-2 benchmark, at about 10–50 ms of refinement per batch. No absolute per-dimension UVP values for this method were found on Lacuna. We will therefore rerun its public configuration ourselves, with identical benchmark pairs, batch sizes, network widths and depths, number of training steps, and hyperparameter search budget. The same L-BFGS implementation and amortizer will be used for every method so that only the potential's parameterization differs.

We also include Wasserstein-2 Generative Networks. It reports 1.5% $L^2$-UVP on 4096-dimensional Gaussians, with non-convex baselines above 50%. This is the reference for the high-dimensional Gaussian setting.

Beating the strongest baseline means two things on the same pairs. First, a bounded-$\kappa$ ICNN must match or improve the MLP-plus-refinement UVP within seed variance. Second, it must have a strictly lower fraction of failed conjugate solves and lower wall-clock time per step. Matching the MLP on accuracy alone, while keeping uniqueness and certificates, would already overturn the "convex costs accuracy" conclusion.

Two ablations isolate the key ingredient. The first adds only the lower bound $\mu$, which is essentially the Convex Potential Flows recipe. The second adds only the upper bound $L$. If the lower bound alone recovers most of the gain, the contribution shrinks to the certificate and stopping rule, and we will report it that way.

Why not just…?

Why not just use a non-convex MLP potential with L-BFGS refinement, since it already wins? This is the main threat. On amortizing convex conjugates for optimal transport shows it often achieves lower transport error than ICNNs. Its weakness is that the conjugate problem can have saddle points and multiple minima. When the Hessian at the returned point is indefinite, conjugate gradient does not apply and implicit Jacobians are undefined. The $\kappa$ sweep settles the question. We will report the MLP's UVP alongside the rate of solves that end at points with negative-curvature directions, detected by Lanczos. If the MLP stays clearly ahead of every bounded-$\kappa$ ICNN, then expressivity rather than conditioning explains the gap, and our central hypothesis is refuted.

Why not just add $\tfrac{\mu}{2}\|x\|^2$ and run conjugate gradient, as Convex Potential Flows does? A lower bound makes the Hessian invertible but leaves $L$, and hence $\kappa$, uncontrolled. The cost of both L-BFGS and conjugate gradient grows with $\kappa$, so the stiffness reported in prior work is untouched. The lower-bound-only ablation tests directly whether the upper bound matters.

Why not just unroll a few solver steps through an unconstrained network? Unrolling stores every iterate, so memory grows with solver depth, as the bilevel survey Investigating Bi-Level Optimization for Learning and Vision documents. Efficient and Modular Implicit Differentiation reports implicit differentiation 4 times faster than unrolling on dataset distillation. Truncated unrolling also gives biased gradients with no bound on the bias. We include unrolling with $K\in\{5,10,20\}$ steps in the structured-prediction experiment and report accuracy against memory.

Why not just use Fenchel-Young losses, which avoid argmin differentiation altogether? Learning Energy Networks with Generalized Fenchel-Young Losses trains energy models using only parameter gradients at the predicted and true outputs, via the envelope theorem. When the loss compares the minimizer to a known target, this is a real competitor, and it may match implicit training. We include it as a baseline in the image-completion experiment and do not claim implicit differentiation must win there. Our certificate still governs the bias of the envelope gradient through $\|\hat x - x^*\|$. The full Jacobian remains necessary when an upstream network must receive gradients through the minimizer, which is the setting in which we report the implicit layer's advantage.

Proposed Experiments and Decisive Checks

Experiment 1: conditioning diagnosis. We train vanilla ICNN potentials on the pairs of the continuous Wasserstein-2 benchmark across the dimensions it covers, up to 64 and beyond. We record Hessian condition numbers at conjugate solutions, L-BFGS iteration counts, and the solve failure rate, and relate them to final $L^2$-UVP. The decisive check is whether condition number predicts both iteration count and UVP across seeds and dimensions better than network width does.

Experiment 2: the $\kappa$ sweep. We sweep the curvature-bounded ICNN over $\kappa$ from 10 to $10^4$ on the same pairs and on the high-dimensional Gaussian setting. We compare against the baselines above on UVP, wall-clock time per training step, the failure rate of conjugate solves, and the measured error of envelope gradients against a high-precision reference solve. The decisive outcome is an interior optimum in $\kappa$: too small loses expressivity, too large is slow and inaccurate, and the best value matches the MLP-plus-refinement result.

Experiment 3: implicit Jacobians. We train a partially convex ICNN for Olivetti face completion, following Input Convex Neural Networks, with the loss taken on the minimizer itself. There, the bundle-entropy ICNN reports MSE 833.0, against 872.0 for gradient-descent inference and 850.9 for a non-convex network of the same shape. We compare four training schemes: the certified implicit layer with adaptive stopping, unrolled training, Fenchel-Young training, and the original method. We plot test MSE against backward-pass compute and memory. We also verify that the certified Jacobian error bound holds empirically and report how loose it is relative to errors measured against finite differences at tight tolerance.

Decisive checks for the whole proposal. The proposal succeeds if three things hold together: the bound on the curvature constant $L$ is within a small factor of measured spectra, a bounded-$\kappa$ ICNN closes the transport gap to non-convex potentials, and certified stopping reduces backward-pass compute without raising the measured error. It fails cleanly if the MLP's advantage persists at every $\kappa$, which would point to expressivity as the true bottleneck.