Analytical bounds on the local Lipschitz constants of affine-ReLU functions

• URL: http://arxiv.org/abs/2008.06141v1
• Date: Fri, 14 Aug 2020 00:23:21 GMT
• Title: Analytical bounds on the local Lipschitz constants of affine-ReLU functions
• Authors: Trevor Avant, Kristi A. Morgansen
• Abstract summary: We mathematically determine upper bounds on the local Lipschitz constant of an affine-ReLU function. We show how these bounds can be combined to determine a bound on an entire network. We show several examples by applying our results to AlexNet, as well as several smaller networks based on the MNIST and CIFAR-10 datasets.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we determine analytical bounds on the local Lipschitz constants of of affine functions composed with rectified linear units (ReLUs). Affine-ReLU functions represent a widely used layer in deep neural networks, due to the fact that convolution, fully-connected, and normalization functions are all affine, and are often followed by a ReLU activation function. Using an analytical approach, we mathematically determine upper bounds on the local Lipschitz constant of an affine-ReLU function, show how these bounds can be combined to determine a bound on an entire network, and discuss how the bounds can be efficiently computed, even for larger layers and networks. We show several examples by applying our results to AlexNet, as well as several smaller networks based on the MNIST and CIFAR-10 datasets. The results show that our method produces tighter bounds than the standard conservative bound (i.e. the product of the spectral norms of the layers' linear matrices), especially for small perturbations.

Related papers

• Generalization Bounds and Model Complexity for Kolmogorov-Arnold Networks [1.5850926890180461]
  Kolmogorov-Arnold Network (KAN) is a network structure recently proposed by Liu et al. Work provides a rigorous theoretical analysis of KAN by establishing generalization bounds for KAN equipped with activation functions.
  arXiv  Detail & Related papers  (2024-10-10T15:23:21Z)
• Approximation Error and Complexity Bounds for ReLU Networks on Low-Regular Function Spaces [0.0]
  We consider the approximation of a large class of bounded functions, with minimal regularity assumptions, by ReLU neural networks. We show that the approximation error can be bounded from above by a quantity proportional to the uniform norm of the target function.
  arXiv  Detail & Related papers  (2024-05-10T14:31:58Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration [122.51142131506639]
  We introduce a precise, fast, and differentiable upper bound for the spectral norm of convolutional layers using circulant matrix theory. We show through a comprehensive set of experiments that our approach outperforms other state-of-the-art methods in terms of precision, computational cost, and scalability. It proves highly effective for the Lipschitz regularization of convolutional neural networks, with competitive results against concurrent approaches.
  arXiv  Detail & Related papers  (2023-05-25T15:32:21Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  We first show that a three-layer neural network can be designed to approximate an indicator function over a compact set. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. We prove the universal approximation property of three-layer ReLU networks using our topological approach.
  arXiv  Detail & Related papers  (2023-05-25T14:17:15Z)
• Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation [79.13041340708395]
  Lipschitz constants are connected to many properties of neural networks, such as robustness, fairness, and generalization. Existing methods for computing Lipschitz constants either produce relatively loose upper bounds or are limited to small networks. We develop an efficient framework for computing the $ell_infty$ local Lipschitz constant of a neural network by tightly upper bounding the norm of Clarke Jacobian.
  arXiv  Detail & Related papers  (2022-10-13T22:23:22Z)
• Approximation speed of quantized vs. unquantized ReLU neural networks and beyond [0.0]
  We consider general approximation families encompassing ReLU neural networks. We use $infty$-encodability to guarantee that ReLU networks can be uniformly quantized. We also prove that ReLU networks share a common limitation with many other approximation families.
  arXiv  Detail & Related papers  (2022-05-24T07:48:12Z)
• Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds [99.23098204458336]
  Certified robustness is a desirable property for deep neural networks in safety-critical applications. We show that our method consistently outperforms state-of-the-art methods on MNIST and TinyNet datasets.
  arXiv  Detail & Related papers  (2021-11-02T06:44:10Z)
• Analytical bounds on the local Lipschitz constants of ReLU networks [0.0]
  We do so by deriving Lipschitz constants and bounds for ReLU, affine-ReLU, and max pooling functions. Our method produces the largest known bounds on minimum adversarial perturbations for large networks such as AlexNet and VGG-16.
  arXiv  Detail & Related papers  (2021-04-29T21:57:47Z)
• Approximating Lipschitz continuous functions with GroupSort neural networks [3.416170716497814]
  Recent advances in adversarial attacks and Wasserstein GANs have advocated for use of neural networks with restricted Lipschitz constants. We show in particular how these networks can represent any Lipschitz continuous piecewise linear functions. We also prove that they are well-suited for approximating Lipschitz continuous functions and exhibit upper bounds on both the depth and size.
  arXiv  Detail & Related papers  (2020-06-09T13:37:43Z)
• Exactly Computing the Local Lipschitz Constant of ReLU Networks [98.43114280459271]
  The local Lipschitz constant of a neural network is a useful metric for robustness, generalization, and fairness evaluation. We show strong inapproximability results for estimating Lipschitz constants of ReLU networks. We leverage this algorithm to evaluate the tightness of competing Lipschitz estimators and the effects of regularized training on the Lipschitz constant.
  arXiv  Detail & Related papers  (2020-03-02T22:15:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.