Robust Implicit Networks via Non-Euclidean Contractions

Saber Jafarpour, A. S. Davydov, Anton V. Proskurnikov, Francesco Bullo

TL;DR

This paper introduces NEMON, a novel framework for designing robust and well-posed implicit neural networks using non-Euclidean contraction theory. By leveraging the $\ell_{\infty}$-norm and one-sided Lipschitz constants, NEMON offers improved stability, faster convergence, and enhanced robustness against adversarial attacks compared to existing methods.

What Problem Does This Paper Address?

Implicit neural networks (also known as deep equilibrium models) offer advantages like improved accuracy and reduced memory footprint by defining layers implicitly through fixed-point equations. However, these models can suffer from ill-posedness (multiple or no solutions to the fixed-point equation) and convergence instability during training. Furthermore, their inherent flexibility can lead to brittle input-output behavior, making them vulnerable to adversarial perturbations. Existing methods for ensuring well-posedness and robustness often rely on Euclidean norms, which may not be optimal for certain types of perturbations or network architectures.

Methods

The core contribution of this paper is the Non-Euclidean Monotone Operator Network (NEMON) framework. Key elements include:

  • Non-Euclidean Contraction Theory ($\ell_{\infty}$-norm): The authors extend contraction theory to the $\ell_{\infty}$-norm, which is shown to be more informative for certain robustness analyses than the standard $\ell_2$-norm.
  • One-Sided Lipschitz Constants: They introduce and utilize one-sided Lipschitz constants in the $\ell_{\infty}$ context to establish novel conditions for well-posedness of the fixed-point equations. This provides a more flexible condition than traditional Lipschitz continuity.
  • Average Iteration: An accelerated average iteration method is proposed for computing fixed points, leading to faster convergence.
  • Input-Output Lipschitz Estimates: The framework provides explicit estimates for input-output Lipschitz constants, crucial for understanding and controlling network sensitivity.
  • Training Framework: A training problem is designed with well-posedness and convergence as constraints. Crucially, the input-output Lipschitz constant is used as a regularizer to promote robustness.
  • Parametrization: A novel parametrization for weight matrices is introduced that directly enforces the $\ell_{\infty}$-norm based well-posedness condition, leading to a larger search space and improved training.

Datasets

The proposed NEMON framework was evaluated on the following standard image classification datasets:

  • MNIST: A dataset of handwritten digits.
  • CIFAR-10: A dataset of 32x32 color images in 10 classes.

Key Insights and Ideas

  • $\ell_{\infty}$-norm for Robustness: The paper highlights that the $\ell_{\infty}$-norm is often more relevant than the $\ell_2$-norm for analyzing robustness against certain types of adversarial perturbations, particularly widespread, entrywise small perturbations.
  • One-Sided Lipschitz as a Key to Well-Posedness: By extending one-sided Lipschitz conditions to the $\ell_{\infty}$-norm, the authors provide a more general and effective criterion for ensuring that implicit neural networks have unique and stable solutions.
  • Accelerated Convergence: The proposed average iteration method, particularly when tailored for $\ell_{\infty}$ norms, offers significant speedups in convergence compared to standard fixed-point iteration techniques.
  • Lipschitz Regularization for Robustness: Directly incorporating input-output Lipschitz constants into the training objective is shown to be an effective strategy for improving adversarial robustness.

Key Results

  • Improved Accuracy: NEMON models achieved competitive or superior accuracy on MNIST and CIFAR-10 compared to state-of-the-art implicit deep learning models and Monotone Operator Networks (MON). For instance, on MNIST, NEMON achieved an average best accuracy of 0.9772, comparable to MON (0.9762) and better than implicit deep learning (0.9721).
  • Enhanced Robustness: NEMON demonstrated significantly improved robustness against various adversarial attacks (continuous image inversion, uniform additive $\ell_{\infty}$-noise, FGSM, PGDM) on both MNIST and CIFAR-10. Regularized NEMON models showed a substantial decrease in their input-output Lipschitz constants, leading to much higher accuracy under perturbations. For example, on CIFAR-10, regularized NEMON with $\lambda=10^{-4}$ achieved 66% accuracy at a perturbation of 0.1, while MON achieved 35%.
  • Faster Training: The average iteration method contributed to efficient training, with NEMON often requiring fewer forward and backward iterations per epoch compared to other methods.

Limitations and Future Work

  • Activation Functions: While the paper shows extensions for non-differentiable activation functions, the core theoretical results are derived for differentiable functions. The paper notes that conclusions still hold for certain classes of non-differentiable functions, but this might be an area for further generalization.
  • Generalizability of $\ell_{\infty}$: While $\ell_{\infty}$ is shown to be beneficial, the paper focuses on specific types of perturbations. Further research could explore its effectiveness against a broader range of adversarial attacks.
  • Future Directions: The authors suggest that their framework is applicable to studying stability and robustness of implicit learning models with additional structures, such as graph neural networks.

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 A. S. Davydov and Anton V. 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