Abstract: Important research efforts have focused on the design and training of neural networks with a controlled Lipschitz constant. The goal is to increase and sometimes guarantee the robustness against adversarial attacks. Recent promising techniques draw inspirations from different backgrounds to design 1-Lipschitz neural networks, just to name a few: convex potential layers derive from the discretization of continuous dynamical systems, Almost-Orthogonal-Layer proposes a tailored method for matrix rescaling. However, it is today important to consider the recent and promising contributions in the field under a common theoretical lens to better design new and improved layers. This paper introduces a novel algebraic perspective unifying various types of 1-Lipschitz neural networks, including the ones previously mentioned, along with methods based on orthogonality and spectral methods. Interestingly, we show that many existing techniques can be derived and generalized via finding analytical solutions of a common semidefinite programming (SDP) condition. We also prove that AOL biases the scaled weight to the ones which are close to the set of orthogonal matrices in a certain mathematical manner. Moreover, our algebraic condition, combined with the Gershgorin circle theorem, readily leads to new and diverse parameterizations for 1-Lipschitz network layers. Our approach, called SDP-based Lipschitz Layers (SLL), allows us to design non-trivial yet efficient generalization of convex potential layers. Finally, the comprehensive set of experiments on image classification shows that SLLs outperforms previous approaches on natural and certified accuracy.
Introduction
Deep neural networks are notoriously fragile; small, imperceptible "adversarial" perturbations to an input can cause them to make wild misclassifications. To build trust in high-stakes applications, researchers seek certified robustness—a mathematical guarantee that a model's prediction remains constant within a defined "safety bubble" around an input.
A primary strategy for achieving this is ensuring that each layer of the network is 1-Lipschitz, meaning the layer does not amplify the distance between inputs. While various methods exist to enforce this constraint—such as Spectral Normalization (SN), Orthogonal layers, and Convex Potential Layers (CPL)—they have historically been treated as a disparate "bag of tricks." This work addresses the lack of a common theoretical framework, providing a unified algebraic perspective that enables the systematic design of more expressive and efficient robust layers.
The SDP Framework for Lipschitz Layers
The authors introduce a unifying perspective based on Semidefinite Programming (SDP). They demonstrate that many 1-Lipschitz layers are specific analytical solutions to a common matrix inequality:
$$W^\top W \preceq T$$
where $W$ is the weight matrix and $T$ is a diagonal scaling matrix. This framework unifies several existing techniques:
- Spectral Normalization (SN): Employs a simple scalar $T$.
- Almost-Orthogonal-Layers (AOL): Uses a specific diagonal $T$ derived from the absolute sums of the weights.
- Convex Potential Layers (CPL): Utilizes the same $T$ as SN but within a residual structure.
Furthermore, the authors provide a rigorous proof that the scaling used in AOL is mathematically optimal for making scaled weights as close to "orthogonal" as possible, explaining its effectiveness in preventing vanishing gradients.
SDP-based Lipschitz Layers (SLL)
Leveraging the Gershgorin circle theorem, the authors derive a new, more general parameterization for $T$ that incorporates learnable variables ($q_i$). This approach, termed SDP-based Lipschitz Layers (SLL), allows the model to adaptively "loosen" the Lipschitz constraint where it is less critical, thereby increasing expressive power while strictly maintaining the 1-Lipschitz guarantee.
Unlike previous methods that may require computationally expensive Singular Value Decompositions (SVD) or matrix inversions during training, SLL utilizes simple analytical formulas that scale efficiently to large convolutional networks.
Experimental Results
The SLL approach was evaluated on standard image classification benchmarks: CIFAR-10, CIFAR-100, and TinyImageNet.
State-of-the-Art Robustness
SLL consistently outperformed previous methods (AOL, CPL, Cayley, SOC) in certified robust accuracy. As shown in Figure 1, SLL X-Large achieved a provable accuracy of 65.8% on CIFAR-10 at a perturbation radius of $\epsilon=36/255$, surpassing the previous state-of-the-art of 64.4% (CPL XL).
Scalability and Efficiency
SLL models demonstrate competitive training times and scale well to more complex datasets. On CIFAR-100 and TinyImageNet, SLL variants maintain high provable accuracy even at larger perturbation radii where competing methods like Local-Lip-B see significant performance degradation.
Conclusion
By framing the design of 1-Lipschitz layers as a structured optimization problem via SDP, this work moves beyond heuristic-based robust architecture design. SLL provides a flexible, efficient, and high-performing family of layers that set new benchmarks for certified robustness. While a gap remains between the natural accuracy of 1-Lipschitz networks and unconstrained models, the SLL framework offers a clear path forward for developing more expressive and provably secure AI systems.
Summary updated