Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees

Abstract:We develop a certified continuation framework for equilibrium computation and for training deep equilibrium networks (DEQs), with training formulated as interpolation to accuracy $2^{-b}$. For inference, compact input homotopy selects a unique branch from a supplied start root, and a rounded Newton tracker follows it under certified boundary, conditioning, derivative, and tube-radius bounds. For training, we augment local-plus-low-rank recurrence with programmable dormant bilinear rank-one channels. Loaded Tikhonov solves diagnose a failed interpolation pass without spectral decomposition; an output-preserving repair aligned with the pass residual supplies the required direction. Training requires certified gate realization and column stability on each pass region, well-posed inference, and finite-update error budgets. With polynomial geometric, encoding, precision, and complete backend budgets, both certified inference and training have bit cost $O(\operatorname{poly}(L+b))$, where $L$ is the encoded instance length. The trainer uses $O(b+\ell)$ passes and reserve channels from an initial residual bounded by $2^\ell$. These guarantees concern a certified promise class. Lean 4 verifies the quantitative core and concrete inference backend; numerical comparisons illustrate the loaded mechanism.

Machine Learning (stat.ML); Machine Learning (cs.LG)

I.2.6; G.1.6; F.2.1

arXiv:2609.16485 [stat.ML]

(or arXiv:2609.16485v1 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2609.16485 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

LLENLean_all.lean

feedforward_lora.py

tikhonov_vs_pseudoarc.py

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.