Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
Abstract
We develop a certified continuation framework for inference and training in deep equilibrium networks (DEQs), with training posed as interpolation to accuracy 2−b. For inference, input homotopy selects an equilibrium branch from a supplied start root, and a rounded tracker follows it under quantitative conditioning, derivative, boundary, and tube-radius certificates. The framework includes structured factorized certificates, sequential block elimination, inheritance of contraction guarantees in adapted coordinates, and bordered continuation through simple folds. For smooth multidimensional DEQs, including tanh networks, rational local tests can construct and validate oriented continuation charts under explicit geometric promises. For training, programmable dormant bilinear rank-one channels provide output-preserving residual-aligned repairs. Loaded Tikhonov solves diagnose insufficient parameter-to-output directions, while certified gate realization, column stability, well-posed inference, and finite-update error budgets control each pass. Under polynomially bounded certificate, encoding, precision, and backend costs, both inference and training have bit complexity O(poly(L+b)), where L is the encoded instance length; training uses O(b+ℓ) passes and reserve channels from an initial residual bounded by 2ℓ. A budgeted implementation returns either certified success or inconclusive termination. The quantitative core and local certificate machinery are machine-checked in Lean 4, while numerical experiments illustrate the training mechanism.
Related
- A certified continuation machine for Mahler measure identities at CM points, with twelve new proofs of conjectures of Samart
- Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Risk-Averse Bayesian Games with an Unknown Type Distribution: Bayesian Learning, Equilibrium Analysis, and Finite-Sample Guarantees
- Data-Driven MPC with Adaptively Sampled Non-Expert Demonstrations: Performance Guarantees and Sample Complexity
BibTeX
@misc{borisevich2026certified,
title = {{Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees}},
author = {Alex Borisevich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16485},
eprint = {2609.16485},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16485},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
AU - Alex Borisevich
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.16485
UR - https://arxiv.org/abs/2609.16485
AB - We develop a certified continuation framework for inference and training in deep equilibrium networks (DEQs), with training posed as interpolation to accuracy 2^−b. For inference, input homotopy selects an equilibrium branch from a supplied start root, and a rounded tracker follows it under quantitative conditioning, derivative, boundary, and tube-radius certificates. The framework includes structured factorized certificates, sequential block elimination, inheritance of contraction guarantees in adapted coordinates, and bordered continuation through simple folds. For smooth multidimensional DEQs, including tanh networks, rational local tests can construct and validate oriented continuation charts under explicit geometric promises. For training, programmable dormant bilinear rank-one channels provide output-preserving residual-aligned repairs. Loaded Tikhonov solves diagnose insufficient parameter-to-output directions, while certified gate realization, column stability, well-posed inference, and finite-update error budgets control each pass. Under polynomially bounded certificate, encoding, precision, and backend costs, both inference and training have bit complexity O(poly(L+b)), where L is the encoded instance length; training uses O(b+ℓ) passes and reserve channels from an initial residual bounded by 2^ℓ. A budgeted implementation returns either certified success or inconclusive termination. The quantitative core and local certificate machinery are machine-checked in Lean 4, while numerical experiments illustrate the training mechanism.
ER -