Lipschitz constant estimation of Neural Networks via sparse polynomial optimization

2020/04/18 by Fabian Latorre, Latorre, Fabian, Paul Rolland +3 · 10 citations
Computer Science · Engineering · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2004.08688

openalex publication_date 2020/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bounds on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use the sparse connectivity of a network, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the ℓ_∞-Lipschitz constant, our approach yields superior estimates, compared to baselines available in the literature.

Citations

• Gradient-based learning applied to document recognition
• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
• Limitations of the Lipschitz constant as a defense against adversarial\n examples

Cited by

• Nesterov-Accelerated Robust Federated Learning Over Byzantine Adversaries
• Delving into Cascaded Instability: A Lipschitz Continuity View on Image Restoration and Object Detection Synergy
• CS-TSSOS: Correlative and Term Sparsity for Large-Scale Polynomial Optimization
• ECLipsE-Gen-Local: Efficient Compositional Local Lipschitz Estimates for Deep Neural Networks
• Train Large, Deploy Compact: Structured Compression for Compact Low-Rank Adaptation
• Zubov-Net: Adaptive Stability for Neural ODEs Reconciling Accuracy with Robustness
• Stochastic Sample Approximations of (Local) Moduli of Continuity
• Towards Understanding the Data Dependency of Mixup-style Training
• What training reveals about neural network complexity
• Orthogonalizing Convolutional Layers with the Cayley Transform

Related

• Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks
• Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks
• Local Lipschitz Bounds of Deep Neural Networks
• Semialgebraic Optimization for Lipschitz Constants of ReLU Networks
• Lipschitz regularity of deep neural networks: analysis and efficient estimation