Research map / Learning theory and algorithms / Sample complexity
Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives novel quadratic constraints for GroupSort, MaxMin, and Householder activations (using sum preservation and 1-Lipschitzness) to extend LipSDP beyond slope-restricted activations, giving tighter l2 and l∞ Lipschitz bounds for feedforward, residual, and implicit networks.
Problem
Lipschitz constant estimation for neural networks with GroupSort, MaxMin, and Householder activations, which are not slope-restricted on [0,1], so LipSDP cannot be applied directly; naive residual-ReLU rewriting of MaxMin yields overly conservative bounds.
Approach
New quadratic constraints for GroupSort and Householder activations exploit sum preservation within groups and subgroup-wise 1-Lipschitzness, replacing the sector-bound slope-restriction constraint in LipSDP; this yields SDPs for l2 and l∞ bounds across non-residual, residual, and implicit architectures.
Key results
- On MaxMin MNIST networks, LipSDP-NSR gives l2 bounds well below the matrix-product bound, e.g., 22.59 vs 23.46 for 2-layer 16 units and 401.03 vs 780 for 8-layer 32 units, and far below MP for 18-layer networks (17432 vs 73405 for 18-layer 32 units).
- For l∞ bounds LipSDP-NSR is roughly half the equivalence-of-norms bound (e.g., 1058.8 vs 1984.4 for 2-layer 128 units).
- The proposed constraints recover the 1-Lipschitz property of MaxMin, which the residual ReLU LipSDP-RR formulation does not (it gives rho=2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LipSDP-NSR instead of LipSDP-RR | MaxMin network · MNIST, 2-layer 16 units, ℓ2 | Lipschitz bound: 23.92 -> 22.59 | Helped |
| Use LipSDP-NSR instead of LipSDP-RR | MaxMin network · MNIST, 2-layer 16 units, ℓ∞ | Lipschitz bound: 207.3 -> 202.82 | Helped |
| Use LipSDP-NSR instead of the matrix-product bound | MaxMin network · MNIST, 18-layer 32 units, ℓ2 | Lipschitz bound: 73405 -> 17432 | Helped |
| Use LipSDP-NSR instead of the matrix-product bound | MaxMin network · MNIST, 18-layer 32 units, ℓ∞ | Lipschitz bound: 2.23E+13 -> 1.7599E+05 | Helped |
| Set P=S=0 (ablation) | LipSDP-NSR for residual MaxMin networks · MNIST residual network, 5-layer 32 units, ℓ2 | Lipschitz bound: 29.75 -> 33.04 | Hurt |
| Set S=P=0 (ablation) | LipSDP-NSR for feed-forward GroupSort/Householder networks · Feed-forward networks, ℓ2 | Lipschitz bound | No clear effect |
| Set S=P=0 (ablation) | LipSDP-NSR for feed-forward GroupSort/Householder networks · Feed-forward networks, ℓ∞ | Lipschitz bound | No clear effect |
| Set S=0 while retaining P≠0 (ablation) | LipSDP-NSR for residual networks · MNIST residual networks, ℓ2 | Lipschitz bound: 33.04 -> 29.75 | Helped |
Surprising findings
- Direct LipSDP applied to the residual-ReLU rewriting of MaxMin yields rho=2, failing to recover the well-known 1-Lipschitz property of MaxMin.
- Setting S=P=0 in the SDP is reported to yield the same results as using nonzero (S,P) in preliminary tests.
Limitations
- SDP-based bounds are computationally expensive and scale poorly to large networks, mitigated only by structure-exploiting tricks.
- Gradient norm preserving networks with norm-constrained weights have tight Lipschitz constant 1, so the method is mainly useful for networks trained without weight constraints.
- Solver runtimes grow substantially for large networks, e.g., residual networks with 128 units (over 1000s).
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: Lipschitz upper bound (l2 and l∞) computation time in seconds
Baselines: Sample FGL LipSDP-RR Matrix-Product Equivalence of norms
Builds on: LipSDP quadratic constraint framework from control theory Fazlyab et al. l∞ LipSDP extension residual ReLU rewriting of MaxMin
Closest papers by meaning
- ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks (NeurIPS 2024 · similarity 0.88)
- Some Fundamental Aspects about Lipschitz Continuity of Neural Networks (ICLR 2024 · similarity 0.88)
- A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations (ICML 2025 · similarity 0.88)
- DP-SGD Without Clipping: The Lipschitz Neural Network Way (ICLR 2024 · similarity 0.87)
- Approximation theory for 1-Lipschitz ResNets (NeurIPS 2025 · similarity 0.87)
- A provable control of sensitivity of neural networks through a direct parameterization of the overall bi-Lipschitzness (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.