Robust Implicit Networks via Non-Euclidean Contractions

Saber Jafarpour, Alexander Davydov, Anton Proskurnikov, Francesco Bullo

Implicit neural networks, often referred to as Deep Equilibrium Models (DEQs), represent a paradigm shift in deep learning. Rather than stacking discrete layers, these "infinite-depth" models define their output as the solution to a fixed-point equation: $x = f(x, u)$. While this approach yields incredible memory efficiency and flexibility, it introduces two major vulnerabilities: ill-posedness (the fixed-point equation may lack a unique solution or cause numerical solvers to fail) and brittleness (extreme sensitivity to small, adversarial input perturbations).

Historically, researchers have relied on Euclidean ($\ell_2$) norm constraints to guarantee stability. However, $\ell_2$ constraints are often overly restrictive and fail to capture the widespread, entry-wise nature of many adversarial attacks, where every pixel in an image is altered by a microscopic amount. To overcome these limitations, this paper introduces NEMON (Non-Euclidean Monotone Operator Networks), a novel framework that leverages $\ell_\infty$-norm contraction theory to design well-posed, robust implicit neural networks.

The NEMON Framework

NEMON shifts the focus from standard Euclidean constraints to the weighted $\ell_\infty$ norm, introducing several methodological innovations to stabilize training and certify robustness:

  • One-Sided Lipschitz (osL) Constants: The authors utilize "matrix measures" to establish a new condition for well-posedness. This condition is significantly less conservative than standard Lipschitz constants, allowing for a broader variety of weight matrices during training.
  • Average Iteration for Fixed Points: To reliably solve the fixed-point equation, NEMON employs a damped iteration technique ($y_{k+1} = (1-\alpha)y_k + \alpha F(y_k)$). The authors prove that this method converges even when standard solvers fail and demonstrate how to accelerate it specifically under the $\ell_\infty$ norm.
  • Lipschitz Regularization: By deriving explicit bounds for the network's input-output sensitivity, the authors incorporate these bounds as a regularizer in the loss function. This forces the network to remain "smooth" and highly resistant to input perturbations.
  • Weight Parametrization: The framework introduces a clever parametrization of the weight matrix $A$. This ensures the well-posedness condition is automatically satisfied during training, effectively transforming a complex constrained optimization problem into a manageable unconstrained one.

Key Insights: Why $\ell_\infty$ Matters

The transition to the $\ell_\infty$ norm provides distinct theoretical and practical advantages. First, the $\ell_\infty$ norm is uniquely suited for analyzing entry-wise perturbations. A network robust in $\ell_\infty$ is mathematically guaranteed to withstand small, distributed changes across the entire input signal—a hallmark of modern adversarial attacks.

Furthermore, the $\ell_\infty$ well-posedness condition defines a "polytopic" search space for the network's weights. This space is significantly larger than the restrictive "ball" defined by traditional $\ell_2$ methods, granting the model more freedom to learn complex, high-dimensional patterns without sacrificing stability. Because the framework provides an explicit formula for the input-output Lipschitz constant, practitioners can calculate a strict "safety margin." If an adversarial perturbation falls within this margin, the network's classification is guaranteed to remain unchanged.

Empirical Results

The authors evaluated NEMON on standard computer vision benchmarks, including MNIST (handwritten digits) and CIFAR-10 (object classification), yielding impressive results:

  • Improved Accuracy: On the MNIST dataset, NEMON achieved 97.72% accuracy, outperforming both standard implicit models (97.21%) and existing Monotone Operator Networks (97.62%).
  • Dramatic Robustness Gains: When utilizing Lipschitz regularization, NEMON models exhibited a two-order of magnitude decrease in their input-output Lipschitz constants compared to unregularized baselines.
  • Adversarial Defense: Under image inversion attacks, NEMON maintained significantly higher accuracy than competing models, even as the intensity of the attacks increased.
  • Computational Efficiency: Despite the added theoretical rigor, NEMON's training times remained highly competitive with state-of-the-art implicit models (averaging ~9.8 seconds per epoch on MNIST).

Limitations and Future Directions

While NEMON presents a robust step forward for implicit networks, the authors note a few limitations. The current CIFAR-10 experiments rely on a relatively simple single-layer convolutional structure; scaling this $\ell_\infty$ framework to highly complex, multi-layer implicit architectures remains an open challenge.

Additionally, while the $\ell_\infty$ norm is powerful for specific perturbations, other applications might benefit from different non-Euclidean norms, such as $\ell_1$. The authors suggest their contraction-based framework is flexible enough to be extended to these cases. Finally, they envision applying this stability analysis to Graph Neural Networks (GNNs), a domain where convergence and stability remain persistent hurdles.

Summary updated

Abstract

Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicit-depth learning models where function evaluation is performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability. This paper provides a new framework, which we call Non-Euclidean Monotone Operator Network (NEMON), to design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm $\ell_\infty$. Our framework includes (i) a novel condition for well-posedness based on one-sided Lipschitz constants, (ii) an average iteration for computing fixed-points, and (iii) explicit estimates on input-output Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant as a regularizer. Our $\ell_\infty$ well-posedness condition leads to a larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we evaluate our framework in image classification through the MNIST and the CIFAR-10 datasets. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds. Code is available at https://github.com/davydovalexander/Non-Euclidean_Mon_Op_Net.
BibTeX
@inproceedings{jafarpour2021robust,
  author = {Saber Jafarpour and Alexander Davydov and Anton Proskurnikov and Francesco Bullo},
  title = {{Robust Implicit Networks via Non-Euclidean Contractions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=SwfsoPuGYku},
}
Figure