Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification

• URL: http://arxiv.org/abs/2410.06816v3
• Date: Thu, 25 Sep 2025 13:51:41 GMT
• Title: Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification
• Authors: Yuhao Mao, Yani Zhang, Martin Vechev,
• Abstract summary: We present the first rigorous analysis of the expressiveness of multi-neuron relaxations.<n>We show that they are inherently incomplete, even when allocated sufficient resources to capture finitely many neurons and optimally layers.<n>Our findings establish a foundation for multi-neuron relaxations and point to new directions for certified robustness.
• Score: 5.05356759900008
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural network certification methods heavily rely on convex relaxations to provide robustness guarantees. However, these relaxations are often imprecise: even the most accurate single-neuron relaxation is incomplete for general ReLU networks, a limitation known as the \emph{single-neuron convex barrier}. While multi-neuron relaxations have been heuristically applied to address this issue, two central questions arise: (i) whether they overcome the convex barrier, and if not, (ii) whether they offer theoretical capabilities beyond those of single-neuron relaxations. In this work, we present the first rigorous analysis of the expressiveness of multi-neuron relaxations. Perhaps surprisingly, we show that they are inherently incomplete, even when allocated sufficient resources to capture finitely many neurons and layers optimally. This result extends the single-neuron barrier to a \textit{universal convex barrier} for neural network certification. On the positive side, we show that completeness can be achieved by either (i) augmenting the network with a polynomial number of carefully designed ReLU neurons or (ii) partitioning the input domain into convex sub-polytopes, thereby distinguishing multi-neuron relaxations from single-neuron ones which are unable to realize the former and have worse partition complexity for the latter. Our findings establish a foundation for multi-neuron relaxations and point to new directions for certified robustness, including training methods tailored to multi-neuron relaxations and verification methods with multi-neuron relaxations as the main subroutine.

Related papers

• Robust Spiking Neural Networks Against Adversarial Attacks [49.08210314590693]
  Spiking Neural Networks (SNNs) represent a promising paradigm for energy-efficient neuromorphic computing.<n>In this study, we theoretically demonstrate that threshold-neighboring spiking neurons are the key factors limiting the robustness of directly trained SNNs.<n>We find that these neurons set the upper limits for the maximum potential strength of adversarial attacks and are prone to state-flipping under minor disturbances.
  arXiv  Detail & Related papers  (2026-02-24T05:06:12Z)
• NOBLE -- Neural Operator with Biologically-informed Latent Embeddings to Capture Experimental Variability in Biological Neuron Models [68.89389652724378]
  NOBLE is a neural operator framework that learns a mapping from a continuous frequency-modulated embedding of interpretable neuron features to the somatic voltage response induced by current injection.<n>It predicts distributions of neural dynamics accounting for the intrinsic experimental variability.<n>NOBLE is the first scaled-up deep learning framework validated on real experimental data.
  arXiv  Detail & Related papers  (2025-06-05T01:01:18Z)
• NeuronSeek: On Stability and Expressivity of Task-driven Neurons [19.773883759021764]
  Prototyping task-driven neurons (referred to as NeuronSeek) employs symbolic regression (SR) to discover the optimal neuron formulation.<n>This work replaces symbolic regression with tensor decomposition (TD) to discover optimal neuronal formulations.<n>We establish theoretical guarantees that modifying the aggregation functions with common activation functions can empower a network with a fixed number of parameters to approximate any continuous function with an arbitrarily small error.
  arXiv  Detail & Related papers  (2025-06-01T01:36:27Z)
• Convex Formulations for Training Two-Layer ReLU Neural Networks [21.88871868680998]
  Non-layer, NP-hard optimization problems are crucial for machine learning models. We introduce a semidefinite relaxation that can be solved in a finite-width two neural network.
  arXiv  Detail & Related papers  (2024-10-29T17:53:15Z)
• Shallow ReLU neural networks and finite elements [1.3597551064547502]
  We show that piecewise linear functions on a convex polytope mesh can be represented by two-hidden-layer ReLU neural networks in a weak sense. The numbers of neurons of the two hidden layers required to weakly represent are accurately given based on the numbers of polytopes and hyperplanes involved in this mesh.
  arXiv  Detail & Related papers  (2024-03-09T06:12:06Z)
• Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations [52.031701581294804]
  Lipschitz bounds for neural networks can be computed with upper time preservation guarantees. Our paper bridges the gap and extends Lipschitz beyond slope-restricted activation functions. Our proposed analysis is general and provides a unified approach for estimating $ell$ and $ell_infty$ Lipschitz bounds.
  arXiv  Detail & Related papers  (2024-01-25T09:23:31Z)
• Expressivity of ReLU-Networks under Convex Relaxations [7.043624904936254]
  We conduct the first in-depth study on the expressive power of ReLU networks across all commonly used convex relaxations. We show that: (i) more advanced relaxations allow a larger class of univariate functions to be expressed as precisely analyzable ReLU networks, (ii) more precise relaxations can allow exponentially larger solution spaces of ReLU networks encoding the same functions, and (iii) even using the most precise single-neuron relaxations, it is impossible to construct precisely analyzable ReLU networks.
  arXiv  Detail & Related papers  (2023-11-07T14:14:15Z)
• Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs [63.768739279562105]
  We show that for a particular choice of mask weights that do not depend on the learning targets, this kernel is equivalent to the NTK of the gated ReLU network on the training data. A consequence of this lack of dependence on the targets is that the NTK cannot perform better than the optimal MKL kernel on the training set.
  arXiv  Detail & Related papers  (2023-09-26T17:42:52Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  We study the type of solutions to which gradient descent converges when used to train a single hidden-layer multivariate ReLU network with the quadratic loss. We prove that although shallow ReLU networks are universal approximators, stable shallow networks are not.
  arXiv  Detail & Related papers  (2023-06-30T09:17:39Z)
• Benign Overfitting for Two-layer ReLU Convolutional Neural Networks [60.19739010031304]
  We establish algorithm-dependent risk bounds for learning two-layer ReLU convolutional neural networks with label-flipping noise. We show that, under mild conditions, the neural network trained by gradient descent can achieve near-zero training loss and Bayes optimal test risk.
  arXiv  Detail & Related papers  (2023-03-07T18:59:38Z)
• Zonotope Domains for Lagrangian Neural Network Verification [102.13346781220383]
  We decompose the problem of verifying a deep neural network into the verification of many 2-layer neural networks. Our technique yields bounds that improve upon both linear programming and Lagrangian-based verification techniques.
  arXiv  Detail & Related papers  (2022-10-14T19:31:39Z)
• Spiking neural network for nonlinear regression [68.8204255655161]
  Spiking neural networks carry the potential for a massive reduction in memory and energy consumption. They introduce temporal and neuronal sparsity, which can be exploited by next-generation neuromorphic hardware. A framework for regression using spiking neural networks is proposed.
  arXiv  Detail & Related papers  (2022-10-06T13:04:45Z)
• Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound [2.896192909215469]
  We present a novel complete verifier which combines the strengths of both paradigms. It uses multi-neuron relaxations to drastically reduce the number of subproblems generated during the BaB process. An extensive evaluation demonstrates that our verifier achieves a new state-of-the-art on both established benchmarks as well as networks with significantly higher accuracy than previously considered.
  arXiv  Detail & Related papers  (2022-04-30T13:12:33Z)
• 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)
• A Primer on Multi-Neuron Relaxation-based Adversarial Robustness Certification [6.71471794387473]
  adversarial examples pose a real danger when deep neural networks are deployed in the real world. We develop a unified mathematical framework to describe relaxation-based robustness certification methods.
  arXiv  Detail & Related papers  (2021-06-06T11:59:27Z)
• Adaptive Rational Activations to Boost Deep Reinforcement Learning [68.10769262901003]
  We motivate why rationals are suitable for adaptable activation functions and why their inclusion into neural networks is crucial. We demonstrate that equipping popular algorithms with (recurrent-)rational activations leads to consistent improvements on Atari games.
  arXiv  Detail & Related papers  (2021-02-18T14:53:12Z)
• And/or trade-off in artificial neurons: impact on adversarial robustness [91.3755431537592]
  Presence of sufficient number of OR-like neurons in a network can lead to classification brittleness and increased vulnerability to adversarial attacks. We define AND-like neurons and propose measures to increase their proportion in the network. Experimental results on the MNIST dataset suggest that our approach holds promise as a direction for further exploration.
  arXiv  Detail & Related papers  (2021-02-15T08:19:05Z)
• Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting [135.0863818867184]
  artificial neural variability (ANV) helps artificial neural networks learn some advantages from natural'' neural networks. ANV plays as an implicit regularizer of the mutual information between the training data and the learned model. It can effectively relieve overfitting, label noise memorization, and catastrophic forgetting at negligible costs.
  arXiv  Detail & Related papers  (2020-11-12T06:06:33Z)
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification [11.10637926254491]
  We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. We design two-time algorithms for neural network verification: a linear-programming-based algorithm that leverages the full power of our relaxation, and a fast propagation algorithm that generalizes existing approaches.
  arXiv  Detail & Related papers  (2020-06-24T22:16:58Z)
• Feature Purification: How Adversarial Training Performs Robust Deep Learning [66.05472746340142]
  We show a principle that we call Feature Purification, where we show one of the causes of the existence of adversarial examples is the accumulation of certain small dense mixtures in the hidden weights during the training process of a neural network. We present both experiments on the CIFAR-10 dataset to illustrate this principle, and a theoretical result proving that for certain natural classification tasks, training a two-layer neural network with ReLU activation using randomly gradient descent indeed this principle.
  arXiv  Detail & Related papers  (2020-05-20T16:56:08Z)
• Improving the Tightness of Convex Relaxation Bounds for Training Certifiably Robust Classifiers [72.56180590447835]
  Convex relaxations are effective for certifying training and neural networks against norm-bounded adversarial attacks, but they leave a large gap between certifiable and empirical robustness. We propose two experiments that can be used to train neural networks that can be trained in higher certified accuracy than non-regularized baselines.
  arXiv  Detail & Related papers  (2020-02-22T20:19:53Z)

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.